package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 环形子数组的最大和
    static class Solution {
        public int maxSubarraySumCircular(int[] nums) {
            // 1) 边界处理
            if (nums == null || nums.length == 0) return 0;

            int n = nums.length;
            if (n == 1) return nums[0];

            // 2) 初始化：动态规划数组和辅助变量
            int[] f = new int[n + 1]; // f[i] 表示以 nums[i-1] 结尾的最大子数组和
            int[] g = new int[n + 1]; // g[i] 表示以 nums[i-1] 结尾的最小子数组和
            f[0] = g[0] = 0;
            int max = Integer.MIN_VALUE / 2; // 记录全局最大子数组和
            int min = Integer.MAX_VALUE / 2; // 记录全局最小子数组和
            int sum = 0; // 数组总和

            // 3) 计算数组总和
            for (int num : nums) {
                sum += num;
            }

            // 4) 动态规划：同时计算最大和最小子数组和
            for (int i = 1; i <= n; i++) {
                // 最大子数组和：要么连接前面，要么从当前开始
                f[i] = Math.max(f[i - 1] + nums[i - 1], nums[i - 1]);
                max = Math.max(max, f[i]);
                // 最小子数组和：要么连接前面，要么从当前开始
                g[i] = Math.min(g[i - 1] + nums[i - 1], nums[i - 1]);
                min = Math.min(min, g[i]);
            }

            // 5) 比较两种情况：不跨边界 vs 跨边界（总和 - 最小子数组和）
            //    特殊情况：如果所有元素都是负数（sum == min），返回 max
            return sum == min ? max : Math.max(max, sum - min);
        }
    }
}